package srcInterviewPrep;

import java.util.ArrayDeque;
import java.util.ArrayList;
import java.util.Deque;
import java.util.HashMap;
import java.util.LinkedList;
import java.util.List;

public final class TopologicalSort
{
    public static List<Vertex> SortTopologically(List<Vertex> vertices)
    {
        if (vertices == null)
        {
            throw new IllegalArgumentException("Parameter 'vertices' can not be null");
        }
        
        Deque<Vertex> zeroIndegreeVertices = new ArrayDeque<Vertex>();
        
        List<Vertex> sortedVertices = new ArrayList<Vertex>();
        HashMap<Vertex, Integer> indegreeCountMap = new HashMap<Vertex, Integer>();
        
        Initialize(vertices, zeroIndegreeVertices, indegreeCountMap);
        
        while (!zeroIndegreeVertices.isEmpty())
        {
            Vertex v = zeroIndegreeVertices.remove();
            
            sortedVertices.add(v);
            
            UpdateIndegreeCounts(v, indegreeCountMap, zeroIndegreeVertices);
        }
        
        if (!indegreeCountMap.isEmpty())
        {
            throw new RuntimeException("Graph contains a cycle. Cannot sort topologically!");
        }
        
        return sortedVertices;
    }

    private static void UpdateIndegreeCounts(
        Vertex vertex,
        HashMap<Vertex, Integer> indegreeCountMap,
        Deque<Vertex> zeroIndegreeVertices)
    {
        for (Vertex n : vertex.Neighbors())
        {
            int curCount = indegreeCountMap.get(n);
            
            if (curCount == 1)
            {
                zeroIndegreeVertices.add(n);
                indegreeCountMap.remove(n);
            }
            else
            {
                indegreeCountMap.put(n, curCount - 1);
            }
        }
    }
    
    private static void Initialize(
        List<Vertex> vertices,
        Deque<Vertex> zeroIndegreeVertices,
        HashMap<Vertex, Integer> indegreeCountMap)
    {
        for (Vertex v : vertices)
        {
        	if (!indegreeCountMap.containsKey(v))
        	{
        		indegreeCountMap.put(v, 0);
        	}
            
            for (Vertex n : v.Neighbors())
            {
                if (!indegreeCountMap.containsKey(n))
                {
                    indegreeCountMap.put(n, 0);
                }
                
                indegreeCountMap.put(n, indegreeCountMap.get(n) + 1);
            }
        }
        
        for (Vertex v : vertices)
        {
            if (indegreeCountMap.get(v) == 0)
            {
                zeroIndegreeVertices.add(v);
                indegreeCountMap.remove(v);
            }
        }
    }
}